{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Font to Fit a Sentence in a Screen"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #string #binary-search #interactive"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #字符串 #二分查找 #交互"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxFont"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #找出适应屏幕的最大字号"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个字符串&nbsp;<code>text</code>。并能够在 宽为 <code>w</code> 高为 <code>h</code> 的屏幕上显示该文本。</p>\n",
    "\n",
    "<p>字体数组中包含按<strong>升序排列</strong>的可用字号，您可以从该数组中选择任何字体大小。</p>\n",
    "\n",
    "<p>您可以使用<code>FontInfo</code>接口来获取任何<strong>可用字体大小</strong>的任何字符的宽度和高度。</p>\n",
    "\n",
    "<p><code>FontInfo</code>接口定义如下：</p>\n",
    "\n",
    "<pre>\n",
    "interface FontInfo {\n",
    "  // 返回 fontSize 大小的字符 ch 在屏幕上的宽度。\n",
    "  // 每调用该函数复杂度为 O(1)\n",
    "  public int getWidth(int fontSize, char ch);\n",
    "\n",
    "  // 返回 fontSize 大小的任意字符在屏幕上的高度。\n",
    "  // 每调用该函数复杂度为 O(1)\n",
    "  public int getHeight(int fontSize);\n",
    "}</pre>\n",
    "\n",
    "<p>一串字符的文本宽度应该是 <strong>每一个字符 </strong>在对应字号<code>(fontSize)</code>下返回的宽度<code>getWidth(fontSize, text[i])</code>的 <strong>总和 </strong>。对应字号的文本高度可由 <code>getHeight(fontSize)</code> 计算得到。</p>\n",
    "\n",
    "<p><strong>请注意：文本最多只能排放一排</strong></p>\n",
    "\n",
    "<p>如果使用相同的参数调用 <code>getHeight</code>&nbsp;或&nbsp;<code>getWidth</code> ，则可以保证 <code>FontInfo</code> 将返回相同的值。</p>\n",
    "\n",
    "<p>同时，对于任何字体大小的&nbsp;<code>fontSize</code> 和任何字符 <code>ch</code> ：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>getHeight(fontSize) &lt;= getHeight(fontSize+1)</code></li>\n",
    "\t<li><code>getWidth(fontSize, ch) &lt;= getWidth(fontSize+1, ch)</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>返回可用于在屏幕上显示文本的最大字体大小。<strong>如果文本不能以任何字体大小显示，则返回-1</strong>。</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> text = \"helloworld\", w = 80, h = 20, fonts = [6,8,10,12,14,16,18,24,36]\n",
    "<strong>输出:</strong> 6\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> text = \"leetcode\", w = 1000, h = 50, fonts = [1,2,4]\n",
    "<strong>输出:</strong> 4\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> text = \"easyquestion\", w = 100, h = 100, fonts = [10,15,20,25]\n",
    "<strong>输出:</strong> -1\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>注意:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= text.length &lt;= 50000</code></li>\n",
    "\t<li><code>text</code> 只包含小写字母</li>\n",
    "\t<li><code>1 &lt;= w &lt;= 10<sup>7</sup></code></li>\n",
    "\t<li><code>1 &lt;= h &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 &lt;= fonts.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= fonts[i] &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>fonts&nbsp;</code>已经按升序排序，且不包含重复项。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-font-to-fit-a-sentence-in-a-screen](https://leetcode.cn/problems/maximum-font-to-fit-a-sentence-in-a-screen/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-font-to-fit-a-sentence-in-a-screen](https://leetcode.cn/problems/maximum-font-to-fit-a-sentence-in-a-screen/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"helloworld\"\\n80\\n20\\n[6,8,10,12,14,16,18,24,36]', '\"leetcode\"\\n1000\\n50\\n[1,2,4]', '\"easyquestion\"\\n100\\n100\\n[10,15,20,25]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is FontInfo's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class FontInfo(object):\n",
    "#    Return the width of char ch when fontSize is used.\n",
    "#    def getWidth(self, fontSize, ch):\n",
    "#        \"\"\"\n",
    "#        :type fontSize: int\n",
    "#        :type ch: char\n",
    "#        :rtype int\n",
    "#        \"\"\"\n",
    "# \n",
    "#    def getHeight(self, fontSize):\n",
    "#        \"\"\"\n",
    "#        :type fontSize: int\n",
    "#        :rtype int\n",
    "#        \"\"\"\n",
    "class Solution:\n",
    "    def maxFont(self, text: str, w: int, h: int, fonts: List[int], fontInfo : 'FontInfo') -> int:\n",
    "\n",
    "        node=-1\n",
    "        fonts=sorted(fonts,key=lambda x:-x)\n",
    "        for f in fonts:\n",
    "            length=0\n",
    "            if fontInfo.getHeight(f)>h:\n",
    "                continue\n",
    "            dic={}\n",
    "            for z in text:\n",
    "                if dic.get(z)==None:\n",
    "                    l=fontInfo.getWidth(f,z)\n",
    "                    dic[z]=l\n",
    "\n",
    "                length+=dic[z]\n",
    "                if length>w:\n",
    "                    break\n",
    "            if length<=w:\n",
    "                node=f\n",
    "                break\n",
    "\n",
    "\n",
    "        return node\n",
    "\n",
    "            \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is FontInfo's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class FontInfo(object):\n",
    "#    Return the width of char ch when fontSize is used.\n",
    "#    def getWidth(self, fontSize, ch):\n",
    "#        \"\"\"\n",
    "#        :type fontSize: int\n",
    "#        :type ch: char\n",
    "#        :rtype int\n",
    "#        \"\"\"\n",
    "# \n",
    "#    def getHeight(self, fontSize):\n",
    "#        \"\"\"\n",
    "#        :type fontSize: int\n",
    "#        :rtype int\n",
    "#        \"\"\"\n",
    "class Solution:\n",
    "    def maxFont(self, text: str, w: int, h: int, fonts: List[int], fontInfo : 'FontInfo') -> int:\n",
    "        def check(mid):\n",
    "            if fontInfo.getHeight(mid) > h:\n",
    "                return False\n",
    "            res = sum(fontInfo.getWidth(mid, x) for x in text)\n",
    "            return res <= w\n",
    "        l, r = 0, len(fonts)-1\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            if check(fonts[mid]):\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        \n",
    "        return fonts[r] if r >= 0 else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is FontInfo's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class FontInfo(object):\n",
    "#    Return the width of char ch when fontSize is used.\n",
    "#    def getWidth(self, fontSize, ch):\n",
    "#        \"\"\"\n",
    "#        :type fontSize: int\n",
    "#        :type ch: char\n",
    "#        :rtype int\n",
    "#        \"\"\"\n",
    "# \n",
    "#    def getHeight(self, fontSize):\n",
    "#        \"\"\"\n",
    "#        :type fontSize: int\n",
    "#        :rtype int\n",
    "#        \"\"\"\n",
    "class Solution:\n",
    "    def maxFont(self, text: str, w: int, h: int, fonts: List[int], fontInfo : 'FontInfo') -> int:\n",
    "        n = len(fonts)\n",
    "        l,r = 0, n-1\n",
    "        cnts = Counter(text)\n",
    "        while l<=r:\n",
    "            mid = (l+r)>>1\n",
    "            f = fonts[mid]\n",
    "            if fontInfo.getHeight(f) <= h and sum(fontInfo.getWidth(f, c) * cnt for c, cnt in cnts.items()) <= w:\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return fonts[r] if r >= 0 else -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is FontInfo's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class FontInfo(object):\n",
    "#    Return the width of char ch when fontSize is used.\n",
    "#    def getWidth(self, fontSize, ch):\n",
    "#        \"\"\"\n",
    "#        :type fontSize: int\n",
    "#        :type ch: char\n",
    "#        :rtype int\n",
    "#        \"\"\"\n",
    "# \n",
    "#    def getHeight(self, fontSize):\n",
    "#        \"\"\"\n",
    "#        :type fontSize: int\n",
    "#        :rtype int\n",
    "#        \"\"\"\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def maxFont(self, text: str, w: int, h: int, fonts: List[int], fontInfo : 'FontInfo') -> int:\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def check(x):\n",
    "            f = fonts[x]\n",
    "            if fontInfo.getHeight(f) > h:\n",
    "                return False\n",
    "            width = 0\n",
    "            for ch in cnt:\n",
    "                width += cnt[ch]*fontInfo.getWidth(f, ch)\n",
    "                if width > w:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        cnt = Counter(text)\n",
    "        m = len(fonts)\n",
    "        i = 0\n",
    "        j = m - 1\n",
    "        while i < j - 1:\n",
    "            mid = i + (j - i) // 2\n",
    "            if check(mid):\n",
    "                i = mid\n",
    "            else:\n",
    "                j = mid\n",
    "        if check(j):\n",
    "            return fonts[j]\n",
    "        if check(i):\n",
    "            return fonts[i]\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is FontInfo's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class FontInfo(object):\n",
    "#    Return the width of char ch when fontSize is used.\n",
    "#    def getWidth(self, fontSize, ch):\n",
    "#        \"\"\"\n",
    "#        :type fontSize: int\n",
    "#        :type ch: char\n",
    "#        :rtype int\n",
    "#        \"\"\"\n",
    "# \n",
    "#    def getHeight(self, fontSize):\n",
    "#        \"\"\"\n",
    "#        :type fontSize: int\n",
    "#        :rtype int\n",
    "#        \"\"\"\n",
    "class Solution:\n",
    "    def maxFont(self, text: str, w: int, h: int, fonts: List[int], fontInfo : 'FontInfo') -> int:\n",
    "\n",
    "        def isgood(mid):\n",
    "            l = sum((fontInfo.getWidth(fonts[mid], a) for a in text))\n",
    "            h2 = fontInfo.getHeight(fonts[mid])\n",
    "            return l <= w and h2 <= h\n",
    "\n",
    "        left = 0\n",
    "        right = len(fonts) - 1\n",
    "        if not isgood(left):\n",
    "            return -1\n",
    "        if isgood(right):\n",
    "            return fonts[right]\n",
    "\n",
    "        while left < right - 1:\n",
    "            mid = (left + right) // 2 \n",
    "            if isgood(mid):\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid\n",
    "        return fonts[left]\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxFont(self, text: str, w: int, h: int, fonts: List[int], fontInfo : 'FontInfo') -> int:\n",
    "        def canFit(fontSize):\n",
    "            total_width = sum(fontInfo.getWidth(fontSize, ch) for ch in text)\n",
    "            total_height = fontInfo.getHeight(fontSize)\n",
    "            return total_width <= w and total_height <= h\n",
    "        \n",
    "        left, right = 0, len(fonts) - 1\n",
    "        res = -1\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if canFit(fonts[mid]):\n",
    "                res = fonts[mid]\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is FontInfo's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class FontInfo(object):\n",
    "#    Return the width of char ch when fontSize is used.\n",
    "#    def getWidth(self, fontSize, ch):\n",
    "#        \"\"\"\n",
    "#        :type fontSize: int\n",
    "#        :type ch: char\n",
    "#        :rtype int\n",
    "#        \"\"\"\n",
    "# \n",
    "#    def getHeight(self, fontSize):\n",
    "#        \"\"\"\n",
    "#        :type fontSize: int\n",
    "#        :rtype int\n",
    "#        \"\"\"\n",
    "class Solution:\n",
    "    def maxFont(self, text: str, w: int, h: int, fonts: List[int], fontInfo : 'FontInfo') -> int:\n",
    "        n = len(fonts)\n",
    "\n",
    "        def check(x):\n",
    "            if fontInfo.getHeight(x) > h:\n",
    "                return False \n",
    "            res = 0\n",
    "            for ch in text:\n",
    "                res += fontInfo.getWidth(x, ch)\n",
    "            return res <= w \n",
    "        \n",
    "        low, high = 0, n - 1\n",
    "        ans = -1\n",
    "        while low <= high:\n",
    "            mid = (low + high) >> 1\n",
    "            if check(fonts[mid]):\n",
    "                ans = fonts[mid]\n",
    "                low = mid + 1\n",
    "            else:\n",
    "                high = mid - 1\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is FontInfo's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class FontInfo(object):\n",
    "#    Return the width of char ch when fontSize is used.\n",
    "#    def getWidth(self, fontSize, ch):\n",
    "#        \"\"\"\n",
    "#        :type fontSize: int\n",
    "#        :type ch: char\n",
    "#        :rtype int\n",
    "#        \"\"\"\n",
    "# \n",
    "#    def getHeight(self, fontSize):\n",
    "#        \"\"\"\n",
    "#        :type fontSize: int\n",
    "#        :rtype int\n",
    "#        \"\"\"\n",
    "\n",
    "\n",
    "# # 二分查找+哈希\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def maxFont(self, text: str, w: int, h: int, fonts: List[int], fontInfo : 'FontInfo') -> int:\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def check(x):\n",
    "            f = fonts[x]\n",
    "            if fontInfo.getHeight(f) > h:\n",
    "                return False\n",
    "\n",
    "            width = 0\n",
    "            for ch in cnt:\n",
    "                width += cnt[ch] * fontInfo.getWidth(f, ch)\n",
    "                if width > w:\n",
    "                    return False\n",
    "\n",
    "            return True\n",
    "\n",
    "\n",
    "        cnt = Counter(text)\n",
    "        m = len(fonts)\n",
    "        i = 0\n",
    "        j = m - 1\n",
    "        while i < j - 1:\n",
    "            mid = (i + j) // 2\n",
    "            if check(mid):\n",
    "                i = mid\n",
    "            else:\n",
    "                j = mid\n",
    "\n",
    "        if check(j):\n",
    "            return fonts[j]\n",
    "\n",
    "        if check(i):\n",
    "            return fonts[i]\n",
    "\n",
    "        return -1\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is FontInfo's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class FontInfo(object):\n",
    "#    Return the width of char ch when fontSize is used.\n",
    "#    def getWidth(self, fontSize, ch):\n",
    "#        \"\"\"\n",
    "#        :type fontSize: int\n",
    "#        :type ch: char\n",
    "#        :rtype int\n",
    "#        \"\"\"\n",
    "# \n",
    "#    def getHeight(self, fontSize):\n",
    "#        \"\"\"\n",
    "#        :type fontSize: int\n",
    "#        :rtype int\n",
    "#        \"\"\"\n",
    "class Solution:\n",
    "    def maxFont(self, text: str, w: int, h: int, fonts: List[int], fontInfo : 'FontInfo') -> int:\n",
    "        n = len(fonts)\n",
    "        l,r = 0, n-1\n",
    "        while l<=r:\n",
    "            mid = (l+r)>>1\n",
    "            f = fonts[mid]\n",
    "            if fontInfo.getHeight(f) <= h and sum(fontInfo.getWidth(f, c) for c in text) <= w:\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return fonts[r] if r >= 0 else -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is FontInfo's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class FontInfo(object):\n",
    "#    Return the width of char ch when fontSize is used.\n",
    "#    def getWidth(self, fontSize, ch):\n",
    "#        \"\"\"\n",
    "#        :type fontSize: int\n",
    "#        :type ch: char\n",
    "#        :rtype int\n",
    "#        \"\"\"\n",
    "# \n",
    "#    def getHeight(self, fontSize):\n",
    "#        \"\"\"\n",
    "#        :type fontSize: int\n",
    "#        :rtype int\n",
    "#        \"\"\"\n",
    "class Solution:\n",
    "    def maxFont(self, text: str, w: int, h: int, fonts: List[int], fontInfo : 'FontInfo') -> int:\n",
    "        @lru_cache(None)\n",
    "        def check(x):\n",
    "            f = fonts[x]\n",
    "            if fontInfo.getHeight(f) > h:\n",
    "                return False\n",
    "            width = 0\n",
    "            for ch in cnt:\n",
    "                width += cnt[ch] * fontInfo.getWidth(f, ch)\n",
    "                if width > w:\n",
    "                    return False\n",
    "            return True\n",
    "        cnt = Counter(text)\n",
    "        m = len(fonts)\n",
    "        i = 0\n",
    "        j = m - 1\n",
    "        while i < j - 1:\n",
    "            mid = i + (j - i) // 2\n",
    "            if check(mid):\n",
    "                i = mid\n",
    "            else:\n",
    "                j = mid\n",
    "        if check(j):\n",
    "            return fonts[j]\n",
    "        if check(i):\n",
    "            return fonts[i]\n",
    "        return -1"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
